<HTML><HEAD><TITLE>CEOI: Problems</TITLE>
</HEAD>
<BODY>
<center>
<h1>CEOI 2002 Day 1 Problem 3</h1>
<h1>A Decorative Fence</h1>
Input file: fence.in <BR>
Output file: fence.out <BR>
Source code: fence.pas/.c/.cpp <BR>
<B>100 points</B> <BR>
Time limit: <B>1 s</B> <BR>
Memory limit: <B>1 MB</B> 
</center>

<P>Richard just finished building his new house. Now the only thing the house 
misses is a cute little wooden fence. He had no idea how to make a wooden fence, 
so he decided to order one. Somehow he got his hands on the ACME<A 
href="http://ipsc.host.sk/footnode.html#foot10" name=tex2html1><SUP>1</SUP></A>Fence Catalogue 2002, the ultimate resource on 
cute little wooden fences. After reading its preface he already knew, what makes 
a little wooden fence cute. 
<P>A wooden fence consists of <I>N</I> wooden planks, placed vertically in a row 
next to each other. A fence looks cute if and only if the following conditions 
are met: 
<P>
<UL>
  <LI>The planks have different lengths, namely 1, 2, ..., <I>N</I> plank length 
  units. 
  <LI>Each plank with two neighbors is either larger than each of its neighbors 
  or smaller than each of them. (Note that this makes the top of the fence 
  alternately rise and fall.) </LI></UL>It follows, that we may uniquely describe 
each cute fence with <I>N</I> planks as a permutation <!-- MATH
$a_1, \dots, a_N$
--><I>a</I><SUB>1</SUB>,..., <I>a</I><SUB>N</SUB> of 
the numbers <!-- MATH
$1, \dots, N$
-->1,..., <I>N</I> such that <!-- MATH
$( for\ all\  i; 1<i<N ) (a_i - a_{i-1})*(a_i - a_{i+1})>0$
-->(<I>for</I>&nbsp;<I>all</I>&nbsp;<I>i</I>;1 
&lt; <I>i</I> &lt; <I>N</I>)(<I>a</I><SUB>i</SUB> - <I>a</I><SUB>i - 
1</SUB>)*(<I>a</I><SUB>i</SUB> - <I>a</I><SUB>i + 1</SUB>) &gt; 0 and vice 
versa, each such permutation describes a cute fence. 
<P>It is obvious, that there are many different cute wooden fences made of 
<I>N</I> planks. To bring some order into their catalogue, the sales manager of 
ACME decided to order them in the following way: Fence <I>A</I> (represented by 
the permutation <!-- MATH
$a_1, \dots, a_N$
--><I>a</I><SUB>1</SUB>,..., 
<I>a</I><SUB>N</SUB>) is in the catalogue before fence <I>B</I> (represented by <!-- MATH
$b_1, \dots, b_N$
--><I>b</I><SUB>1</SUB>,..., <I>b</I><SUB>N</SUB>) 
if and only if there exists such <I>i</I>, that <!-- MATH
$( for\ all\  j<i ) a_j=b_j$
-->(<I>for</I>&nbsp;<I>all</I>&nbsp;<I>j</I> 
&lt; <I>i</I>)<I>a</I><SUB>j</SUB> = <I>b</I><SUB>j</SUB> and <!-- MATH
$(a_i < b_i)$
-->(<I>a</I><SUB>i</SUB> &lt; <I>b</I><SUB>i</SUB>). 
(Also to decide, which of the two fences is earlier in the catalogue, take their 
corresponding permutations, find the first place on which they differ and 
compare the values on this place.) All the cute fences with <I>N</I> planks are 
numbered (starting from 1) in the order they appear in the catalogue. This 
number is called their <EM>catalogue number</EM>. 
<P>
<DIV align=center><img src="image/103.gif"> </DIV>
<P>
<DIV align=center>All cute fences made of <I>N</I> = 4 planks, ordered by their 
catalogue numbers. </DIV>
<P>After carefully examining all the cute little wooden fences, Richard decided 
to order some of them. For each of them he noted the number of its planks and 
its catalogue number. Later, as he met his friends, he wanted to show them the 
fences he ordered, but he lost the catalogue somewhere. The only thing he has 
got are his notes. Please help him find out, how will his fences look like. 

<h2>Input description</h2> 
<P>The first line of the input file contains the number <I>K</I> (<!-- MATH
$1<= K<= 100$
--> 1 &lt; = <I>K</I> &lt; = 100) of input data sets. 
<I>K</I> lines follow, each of them describes one input data set. 
<P>Each of the following <I>K</I> lines contains two integers <I>N</I> and 
<I>C</I> (<!-- MATH
$1<= N<= 20$
--> 1 &lt; = <I>N</I> &lt; = 20), separated by 
a space. <I>N</I> is the number of planks in the fence, <I>C</I> is the 
catalogue number of the fence. 
<P>You may assume, that the total number of cute little wooden fences with 20 
planks fits into a 64-bit signed integer variable (<CODE>long long</CODE> in 
C/C++, <CODE>int64</CODE> in FreePascal). You may also assume that the input is 
correct, in particular that <I>C</I> is at least 1 and it doesn't exceed the 
number of cute fences with <I>N</I> planks. 

<h2>Output description</h2> 
<P>For each input data set output one line, describing the <I>C</I>-th fence 
with <I>N</I> planks in the catalogue. More precisely, if the fence is described 
by the permutation <!-- MATH
$a_1, \dots, a_N$
--><I>a</I><SUB>1</SUB>,..., 
<I>a</I><SUB>N</SUB>, then the corresponding line of the output file should 
contain the numbers <I>a</I><SUB>i</SUB> (in the correct order), separated by 
single spaces. 

<h2>Sample Input</h2>
<PRE>
2
2 1
3 3
</PRE>

<h2>Sample Output</h2>
<PRE>
1 2
2 3 1
</PRE>
</BODY></HTML>
